#pragma once
#include <vector>
#include <iostream>
#include <functional>

template<class T,  class cmp = std::greater<T>>
class Heap
{
private:
    std::vector<T> _heap;
public:
    Heap() = default;
    Heap(const std::vector<T>& v);
    void Push(const T& t);
    void Pop();
    void AdjustUp(int child);
    void AdjustDown(int father, int n);
    void Sort();
    void Print() const;
};
template<class T, class cmp>
void Heap<T, cmp>::Push(const T& t)
{
    _heap.push_back(t);
    AdjustUp(_heap.size()-1);
}

template<class T, class cmp>
void Heap<T, cmp>::Pop()
{
    if(_heap.size() == 0) return;
    std::swap(_heap[0], _heap[_heap.size()-1]);
    _heap.pop_back();
    AdjustDown(0, _heap.size());
}

template<class T, class cmp>
void Heap<T, cmp>::Print() const
{
    for(auto& e : _heap)
    {
        std::cout << e << " ";
    }
    std::cout << std::endl;
}
template<class T, class cmp>
void Heap<T, cmp>::Sort()
{
    int n = _heap.size();
    for(int i = 0; i < n-1; i++)
    {
        std::swap(_heap[0], _heap[n-1-i]);
        AdjustDown(0, n-1-i);
    }
}
template<class T, class cmp>
Heap<T, cmp>::Heap(const std::vector<T>& v):_heap(v)
{
    int n = _heap.size();
    for(int i = n/2; i >= 0; --i)
    {
        AdjustDown(i, n);
    }
    // for(int i = 1; i < n; i++)
    // {
    //     AdjustUp(i);
    // }
}

template<class T, class cmp>
void Heap<T, cmp>::AdjustUp(int child)
{
    if(child == 0) return;
    int father = (child-1)/2;
    while(cmp()(_heap[child], _heap[father]))
    {
        std::swap(_heap[child], _heap[father]);
        child = father;
        father = (child-1)/2;
    }
}

template<class T, class cmp>
void Heap<T, cmp>::AdjustDown(int father, int n)
{
    //1. 堆是完全二叉树，若有孩子，则一定有左孩子，因此先找左孩子
    int left = 2*father + 1;
    while(left < n)
    {
        T child = left;
        //1. 判断是否有右孩子, 如果有，找出孩子
        if(left+1 < n)
        {
            if(cmp()(_heap[left+1], _heap[child])) child = left+1;
        }
        //2. 判断孩子与父亲的大小
        if(cmp()(_heap[child], _heap[father]))
        {
            //3. 如果不符合规则，则交换，并继续向下调整
            std::swap(_heap[child], _heap[father]);
            father = child;
            left = 2*father + 1;
        }
        else return;
    }
}

